子数组最大乘积

[编程题]子数组最大乘积

热度指数：24199 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定一个double类型的数组arr，其中的元素可正可负可0，返回连续子数组累乘的最大乘积。

数据范围：数组大小满足 $0 \le n \le 10$ ，数组中元素满足 $|val| \le 10$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

[-2.5,4,0,3,0.5,8,-1]

输出

12.00000

说明

取连续子数组[3,0.5,8]可得累乘的最大乘积为12.00000

示例2

输入

[1.0,0.0,0.0]

输出

1.00000

说明

取连续子数组[1.0]可得累乘的最大乘积为1.00000

算法知识视频讲解

Python 3

牛客343459580号

class Solution:
def maxProduct(self , arr: List[float]) -> float:
# write code here
save = []
if(len(arr) == 0):
return 0
else:
save.append([arr[0],arr[0]])
for i in range(1,len(arr)):
if(arr[i]!=0):
if(arr[i]>0):
t1 = min(save[-1][0]*arr[i],arr[i])
t2 = max(arr[i],save[-1][1]*arr[i])
save.append([t1,t2])
elif(arr[i]<0):
t1 = min(save[-1][1]*arr[i],arr[i])
t2 = max(arr[i],save[-1][0]*arr[i])
save.append([t1,t2])
#and save[-1][0] and save[-1][1]
else:
save.append([0,0])
#print(save)
return max([i[1] for i in save])

发表于 2022-01-30 15:27:00 回复(0)

Python 3

Joy_9

class Solution:
    def maxProduct(self , nums: List[float]) -> float:
        # write code here
        dp_max=[1]*len(nums)
        dp_max[0]=nums[0]
        dp_min=[1]*len(nums)
        dp_min[0]=nums[0]
        for i in range(1,len(nums)):
            dp_max[i]=max(nums[i],dp_min[i-1]*nums[i],dp_max[i-1]*nums[i])
            dp_min[i]=min(nums[i],dp_max[i-1]*nums[i],dp_min[i-1]*nums[i])
        return max(max(dp_max),max(dp_min))

发表于 2022-01-22 06:19:46 回复(0)

Python 3

牛客35961088号

class Solution:
    def maxProduct(self , arr ):
        # write code here
        if not arr: return 0
        ans = arr[0]
        maxnum = arr[0]
        minnum = arr[0]
        for i in range(1, len(arr)):
            m, n = maxnum, minnum
            maxnum = max(m*arr[i], n*arr[i], arr[i])
            minnum = min(m*arr[i], n*arr[i], arr[i])
            ans = max(ans, maxnum)
        return ans

发表于 2021-08-06 11:27:33 回复(0)